package com.lida.study.common.utils.sudo;

import com.lida.study.sudo.Sudo;
import org.springframework.util.CollectionUtils;

import java.io.*;
import java.util.*;

/**
 * 工具
 * @author lD
 * @date 2019/7/314:00
 */
public class SudoUtils {

    private SudoUtils(){}

    /**
     * 数组维度
     */
    private static int SIZE = 9;

    /**
     * 数组宫格数
     */
    private static int SUDO_SIZE = (int) Math.sqrt(SIZE);

    public static int getSize() {
        return SIZE;
    }

    public static void setSize(int size) {
        SudoUtils.SIZE = size;
        SudoUtils.SUDO_SIZE = (int) Math.sqrt(size);
    }

    public static int getSudoSize() {
        return SUDO_SIZE;
    }

    /**
     * 尝试的最大可能数的个数：就是尝试到个数大于MAX_DEEP的数时就停止尝试
     */
    private static final int MAX_DEEP = 5;

    /**
     * 根据单元格坐标获取X坐标
     * @param a
     * @param b
     * @return
     */
    public static int getXbyUnit(int a, int b) {
        return ((SUDO_SIZE * a) % SIZE + b / SUDO_SIZE);
    }

    /**
     * 根据单元格坐标获取Y坐标
     * @param a
     * @param b
     * @return
     */
    public static int getYbyUnit(int a, int b) {
        return ((a / SUDO_SIZE) * SUDO_SIZE + b % SUDO_SIZE);
    }

    /**
     * 根据横纵坐标获取单元格X坐标
     * @param a
     * @param b
     * @return
     */
    public static int getUnitX(int a, int b) {
        return a / SUDO_SIZE + b / SUDO_SIZE * SUDO_SIZE;
    }

    /**
     * 根据横纵坐标获取单元格Y坐标
     * @param a
     * @param b
     * @return
     */
    public static int getUnitY(int a, int b) {
        return (a * SUDO_SIZE) % SIZE + b % SUDO_SIZE;
    }

    public static Sudo asSudo(String s) throws IllegalAccessException {
        int count = SIZE * SIZE;
        if (s.length() != count) {
            throw new IllegalAccessException("应该是" + count + "位数字");
        }
        int[] ints = new int[count];
        int i = 0;
        for (String c : s.split("")) {
            if (".".equals(c)) {
                ints[i++] = 0;
            } else if ("A".equals(c)){
                ints[i++] = 11;
            } else if ("B".equals(c)){
                ints[i++] = 12;
            } else if ("C".equals(c)){
                ints[i++] = 13;
            } else if ("D".equals(c)){
                ints[i++] = 14;
            } else if ("E".equals(c)){
                ints[i++] = 15;
            } else if ("F".equals(c)){
                ints[i++] = 16;
            } else {
                if (SIZE == 9) {
                    ints[i++] = Integer.parseInt(c);
                } else if (SIZE == 16) {
                    ints[i++] = Integer.parseInt(c) + 1;
                }
            }
        }
        return asSudo(ints);
    }

    private static HashSet<Integer> getAllPossible() {
        if (SIZE == 9) {
            return new HashSet<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));
        } else if (SIZE == 16) {
            return new HashSet<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16));
        }
        return new HashSet<>();
    }

    /**
     * 初始化一个数独
     * @param data
     * @return
     * @throws IllegalAccessException
     */
    public static Sudo asSudo(int... data) throws IllegalAccessException {

        Sudo sudo = new Sudo(SIZE);
        if (data == null || data.length != SIZE * SIZE) {
            throw new IllegalAccessException("数组格式不正确");
        }
        for (int i = 0; i < SIZE; i++) {
            Set<Integer> possible = getAllPossible();
            for (int j = 0; j < SIZE; j++) {
                int data0 = data[SIZE * j + i];
                if (data0 != 0) {
                    if (data0 < 0 || data0 > SIZE) {
                        throw new IllegalAccessException("数组格式不正确");
                    }
                    sudo.add(i, j, data0);
                    if (!possible.remove(data0)) {
                        throw new IllegalAccessException("数组格式不正确");
                    }
                }
            }
            for (int j = 0; j < SIZE; j++) {
                int data0 = data[SIZE * j + i];
                if (data0 == 0) {
                    sudo.set(i, j, possible);
                }
            }
        }
        return sudo;
    }

    /**
     * 检查正确性，首次执行此方法之前需要先执行init()方法
     */
    public static Map.Entry<Boolean, String> check(Sudo sudo) {
        if (sudo == null) {
            return new AbstractMap.SimpleEntry<>(false, "数独实体为空");
        }
        Map<Integer, Map<Integer, Set<Integer>>> data = sudo.getData();
        if (CollectionUtils.isEmpty(data)) {
            return new AbstractMap.SimpleEntry<>(false, "数独为空");
        }
        for (int i = 0; i < SIZE; i++) {
            // 纵排验证
            List<Set<Integer>> value1 = new ArrayList<>();
            // 横排验证
            List<Set<Integer>> value2 = new ArrayList<>();
            // 单元格验证
            List<Set<Integer>> value3 = new ArrayList<>();
            for (int j = 0; j < SIZE; j++) {
                value1.add(sudo.get(i, j));
                value2.add(sudo.get(j, i));
                value3.add(sudo.get(getXbyUnit(i, j), getYbyUnit(i, j)));
            }
            Map.Entry<Boolean, String> check1 = unitCheck(value1);
            if (!check1.getKey()) {
                return check1;
            }
            Map.Entry<Boolean, String> check2 = unitCheck(value2);
            if (!check2.getKey()) {
                return check2;
            }
            Map.Entry<Boolean, String> check3 = unitCheck(value3);
            if (!check3.getKey()) {
                return check3;
            }
        }
        return new AbstractMap.SimpleEntry<>(true, "验证通过");
    }

    private static Map.Entry<Boolean, String> unitCheck(List<Set<Integer>> data) {
        // 单个元素集合
        Set<Integer> singleSet = new HashSet<>();
        for (Set<Integer> datum : data) {
            if (CollectionUtils.isEmpty(datum)) {
                return new AbstractMap.SimpleEntry<>(false, "解题失败");
            } else if (datum.size() == 1) {
                if (!singleSet.add((int) datum.toArray()[0])) {
                    return new AbstractMap.SimpleEntry<>(false, "错误的数独");
                }
            }
        }
        return new AbstractMap.SimpleEntry<>(true, "验证通过");
    }

    /**
     * 初始化数独，填入每个空格中可能的值
     * 该方法仅限自助赋值的用户使用
     */
    @Deprecated
    public static void init(Sudo sudo) {
        for (int i = 0; i < SIZE; i++) {
            Set<Integer> possible = getAllPossible();
            // 排除已知
            for (int j = 0; j < SIZE; j++) {
                Set<Integer> data1 = sudo.get(i, j);
                if (data1.size() == 1) {
                    possible.removeAll(data1);
                }
            }
            // 放入数据
            for (int j = 0; j < SIZE; j++) {
                if (sudo.get(i, j).size() == 0) {
                    sudo.set(i, j, possible);
                }
            }
        }
    }

    /**
     * 排除不可能的值
     * @param sudo
     * @return
     */
    public static Sudo exclude(Sudo sudo) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (!excludeUnit(sudo, i, j)) {
                    // 错了
                    return null;
                }
            }
        }
        return sudo;
    }

    public static boolean excludeUnit(Sudo sudo, int x, int y) {
        boolean b1 = excludeUnit(sudo, x, y, 1);
        boolean b2 = excludeUnit(sudo, x, y, 2);
        boolean b3 = excludeUnit(sudo, x, y, 3);
        return b1 && b2 && b3;
    }

    /**
     * 排除单元组内的可能数，并尝试确定可以确定的数
     * @param sudo 数独实例
     * @param x 坐标
     * @param y 坐标
     * @param type 类型：1纵排；2横排；3单元格
     * @return 是否有变化
     */
    public static boolean excludeUnit(Sudo sudo, int x, int y, int type) {
        Set<Integer> data;
        // 分类型获取需要处理的数据
        if (type == 1 || type == 2) {
            data = sudo.get(x, y);
        } else if (type == 3) {
            data = sudo.get(getXbyUnit(x, y), getYbyUnit(x, y));
        } else {
            return false;
        }
        if (data.size() == 1) {
            return true;
        } else if (data.size() == 0) {
            return false;
        }
        Set<Integer> data1New = new HashSet<>(data);
        // 循环取出对应单元的数据进行比对
        for (int k = 0; k < SIZE; k++) {
            Set<Integer> data1;
            if (type == 1) {
                // 纵排
                if (k == y) {
                    continue;
                }
                data1 = sudo.get(x, k);
            } else if (type == 2) {
                // 横排
                if (k == x) {
                    continue;
                }
                data1 = sudo.get(k, y);
            } else {
                // 单元格
                if (k == y) {
                    continue;
                }
                data1 = sudo.get(getXbyUnit(x, k), getYbyUnit(x, k));
            }
            // 剔除已经确定的值的可能性
            if (data1.size() == 1) {
                data.removeAll(data1);
            }
            // 中间变量剔除确定的和可能的值，如果剩下唯一值，则该值就可以确定
            data1New.removeAll(data1);
        }
        if (data1New.size() == 1) {
            if (type == 1 || type == 2) {
                sudo.set(x, y, data1New);
            } else {
                sudo.set(getXbyUnit(x, y), getYbyUnit(x, y), data1New);
            }
        }
        return true;
    }

    public static boolean isFinished(Sudo sudo) {
        return sudo.getCount() == SIZE * SIZE;
    }

    /**
     * 深度拷贝
     *
     * 不推荐使用，因为感觉有点浪费资源，建议使用其他方式实现克隆功能
     * @param src
     * @param <T>
     * @return
     * @throws IOException
     * @throws ClassNotFoundException
     */
    @SuppressWarnings("unchecked")
    @Deprecated
    public static <T> T deepCopy(T src) {
        ByteArrayOutputStream byteOut = new ByteArrayOutputStream();
        T dest = null;
        try (ObjectOutputStream out = new ObjectOutputStream(byteOut)
        ) {
            out.writeObject(src);
        } catch (IOException e) {
            e.printStackTrace();
        }
        ByteArrayInputStream byteIn = new ByteArrayInputStream(byteOut.toByteArray());
        try (ObjectInputStream in = new ObjectInputStream(byteIn)) {
            dest = (T) in.readObject();
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        }
        return dest;
    }

    public static boolean createChildren(Sudo sudo) {
        return createChildren(sudo, 2);
    }

    private static boolean createChildren(Sudo sudo, int deep) {
        if (deep > MAX_DEEP) {
            return false;
        }
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                Set<Integer> data = sudo.get(i, j);
                if (data.size() == deep) {
                    List<Sudo> list = new ArrayList<>();
                    for (int value : data) {
                        Sudo sudo1 = sudo.clone();
                        sudo1.set(i, j, value);
                        list.add(sudo1);
                    }
                    sudo.setChildren(list);
                    return true;
                }
            }
        }
        // 没有可能数为deep的，则尝试更多可能数的项
        return createChildren(sudo, ++deep);
    }
}
